package com.leetcode.No1834;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution2 {
    public int[] getOrder(int[][] tasks) {
        int[][] array = new int[tasks.length][3];
        for (int i = 0; i < tasks.length; i++) {
            array[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(array, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<int[]> queue = new PriorityQueue<>((a1, a2) -> {
            if (a1[1] != a2[1]) {
                return a1[1] - a2[1];
            }
            return a1[2] - a2[2];
        });
        int[] result = new int[array.length];
        int resultIdx = 0;
        int time = array[0][0];
        int i = 0;
        while (i < array.length || queue.size() > 0) {
            while (i < array.length && array[i][0] <= time) {
                queue.add(array[i++]);
            }
            if (queue.size() == 0 && i < array.length) {
                time = array[i][0];
                continue;
            }
            int[] poll = queue.poll();
            time += poll[1];
            result[resultIdx++] = poll[2];
        }
        return result;
    }

    @Test
    public void test() {
//        int[][] tasks = {{1,2},{2,4},{3,2},{4,1}};
//        int[][] tasks = {{19,13},{16,9},{21,10},{32,25},{37,4},{49,24},{2,15},{38,41},{37,34},{33,6},{45,4},{18,18},{46,39},{12,24}};
//        int[][] tasks = {{23,40},{10,32},{12,18},{10,39},{25,4},{18,12},{38,18},{36,1},{26,5},{45,35},{5,43},{19,19},{46,41},{25,22},{29,17},{26,33},{49,45},{43,44},{50,2}};
//        int[][] tasks = {{19,13},{16,9},{21,10},{32,25},{37,4},{49,24},{2,15},{38,41},{37,34},{33,6},{45,4},{18,18},{46,39},{12,24}};
//        int[][] tasks = {{5,2},{7,2},{9,4},{6,3},{5,10},{1,1}};
        int[][] tasks = {{5,2}, {7,2}, {9,4}, {6,3}, {5,10}, {1,1}};
        System.out.println(Arrays.toString(getOrder(tasks)));
    }
}
